#ifndef _TREE_
#define _TREE_

#include <deque>
#include <queue>
#include <stack>
#include <unordered_map>
#include <vector>
using namespace std;

/**
 * Definition for a binary tree node.
 * */
struct TreeNode {
    int       val;
    TreeNode* left;
    TreeNode* right;
    TreeNode( int x ) : val( x ), left( NULL ), right( NULL ) {}
};

class Tree {
public:
    /*  剑指 Offer 32 - I. 从上到下打印二叉树，从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。
     *  层次遍历。二叉树的 广度优先搜索（BFS)，提示：队列。
     */
    vector< int > levelOrder( TreeNode* root ) {

        vector< int > result;
        if ( root != nullptr ) {
            queue< TreeNode* > queueT;
            TreeNode*          p;
            queueT.push( root );

            while ( !queueT.empty() ) {

                p = queueT.front();

                if ( p->left ) {
                    queueT.push( p->left );
                }

                if ( p->right ) {
                    queueT.push( p->right );
                }
                result.push_back( p->val );
                queueT.pop();
            }
        }

        return result;
    }

    /*分层，层次打印*/
    vector< vector< int > > levelOrder2( TreeNode* root ) {

        vector< vector< int > > result;

        if ( root == nullptr ) {
            return result;
        }

        queue< TreeNode* > queueT;
        queue< int >       order;

        queueT.push( root );
        order.push( 0 );

        TreeNode* p;
        size_t    n;

        while ( !queueT.empty() ) {

            p = queueT.front();
            n = order.front();

            if ( p->left ) {
                queueT.push( p->left );
                order.push( n + 1 );
            }

            if ( p->right ) {
                queueT.push( p->right );
                order.push( n + 1 );
            }

            queueT.pop();
            order.pop();

            if ( ( result.size() - 1 ) != n ) {
                vector< int > newtemp;
                newtemp.push_back( p->val );
                result.push_back( newtemp );
            }
            else {
                result.at( n ).push_back( p->val );
            }
        }

        return result;
    }

    /*请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。提示：双端队列*/
    vector< vector< int > > zigzagLevelOrder( TreeNode* root ) {
        vector< vector< int > > result;

        if ( root == nullptr ) {
            return result;
        }

        queue< TreeNode* > queueT;
        queueT.push( root );

        TreeNode* p;
        size_t    n;
        int       depth = 0;
        while ( !queueT.empty() ) {

            n = queueT.size();

            deque< int > dequeI;

            // for each depth
            for ( size_t i = 0; i < n; i++ ) {

                p = queueT.front();
                queueT.pop();

                if ( p->left ) {
                    queueT.push( p->left );
                }
                if ( p->right ) {
                    queueT.push( p->right );
                }

                if ( depth % 2 != 0 ) {
                    dequeI.push_front( p->val );
                }
                else {
                    dequeI.push_back( p->val );
                }
            }
            depth++;
            result.push_back( vector< int >{ dequeI.begin(), dequeI.end() } );
        }

        return result;
    }

    /* 剑指 Offer 26. 树的子结构
     * 输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构),B是A的子结构， 即 A中有出现和B相同的结构和节点值。
     */
    bool isSubStructure( TreeNode* A, TreeNode* B ) {

        if ( B == nullptr || A == nullptr ) {
            return false;
        }
        if ( A->val == B->val ) {
            if ( dfsEqual( A, B ) ) {
                return true;
            }
        }
        return isSubStructure( A->left, B ) || isSubStructure( A->right, B );
    }

    bool dfsEqual( TreeNode* A, TreeNode* B ) {

        if ( B == nullptr ) {
            return true;
        }
        if ( A == nullptr ) {
            return false;
        }
        if ( A->val == B->val ) {
            return dfsEqual( A->left, B->left ) && dfsEqual( A->right, B->right );
        }
        return false;
    }

    /*剑指 Offer 27. 二叉树的镜像*/
    TreeNode* mirrorTree( TreeNode* root ) {
        if ( root == nullptr ) {
            return nullptr;
        }

        TreeNode* temp = root->left;
        root->left     = root->right;
        root->right    = temp;

        mirrorTree( root->left );
        mirrorTree( root->right );

        return root;
    }

    /*剑指 Offer 28. 对称的二叉树 请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。*/
    bool isSymmetric( TreeNode* root ) {
        if ( root == nullptr ) {
            return true;
        }
        return checkSymmetry( root, root );
    }

    bool checkSymmetry( TreeNode* a, TreeNode* b ) {

        if ( a == nullptr && b == nullptr ) {
            return true;
        }
        if ( a == nullptr ) {
            return false;
        }
        if ( b == nullptr ) {
            return false;
        }
        if ( a->val == b->val ) {

            return checkSymmetry( a->left, b->right ) && checkSymmetry( a->right, b->left );
        }

        return false;
    }
    /*剑指 Offer 33. 二叉搜索树的后序遍历序列
    输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。
    */
    bool verifyPostorder( vector< int >& postorder ) {
        int length = postorder.size();
        if ( postorder.empty() || length == 1 ) {
            return true;
        }

        int          root = INT32_MAX;
        stack< int > stack;
        for ( int i = length - 1; i >= 0; i-- ) {
            int temp = postorder.at( i );

            if ( temp > root ) {
                return false;
            }
            else {
                while ( !stack.empty() && temp < stack.top() ) {
                    root = stack.top();
                    stack.pop();
                }
                stack.push( temp );
            }
        }
        return true;
    }

    // 递归
    bool verifyPostorder2( vector< int >& postorder ) {
        return recurPostorder( postorder, 0, postorder.size() - 1 );
    }

    bool recurPostorder( const vector< int >& postorder, int i, int root ) {
        if ( i >= root ) {
            return true;
        }
        int p = i;
        // left child
        while ( postorder[ p ] < postorder[ root ] ) {
            p++;
        }
        int m = p;
        // right child
        while ( postorder[ p ] > postorder[ root ] ) {
            p++;
        }
        return p == root && recurPostorder( postorder, i, m - 1 ) && recurPostorder( postorder, m, root - 1 );
    }

    /*输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。*/
    TreeNode* buildTree( vector< int >& preorder, vector< int >& inorder ) {
        if ( preorder.empty() ) {
            return nullptr;
        }
        if ( preorder.front() == -1 ) {
            return new TreeNode( -1 );
        }
        for ( size_t i = 0; i < inorder.size(); i++ ) {
            m_inorderMap.emplace( make_pair< int, int >( int( inorder.at( i ) ), i ) );
        }
        return recurBuildTree( preorder, inorder, 0, preorder.size() - 1, 0, inorder.size() - 1 );
    }

    TreeNode* recurBuildTree( vector< int >& preorder, vector< int >& inorder, int preBegin, int preEnd, int inBegin, int inEnd ) {

        if ( preBegin > preEnd || inBegin > inEnd ) {
            return nullptr;
        }

        int       nRoot = preorder[ preBegin ];
        TreeNode* root  = new TreeNode( nRoot );

        int mid          = m_inorderMap[ nRoot ];
        int leftTreelen  = mid - inBegin;
        int rightTreelen = inEnd - mid;

        root->left  = recurBuildTree( preorder, inorder, preBegin + 1, preBegin + leftTreelen, inBegin, mid - 1 );
        root->right = recurBuildTree( preorder, inorder, preEnd - rightTreelen + 1, preEnd, mid + 1, inEnd );

        return root;
    }
    /* 剑指 Offer 68 - II. 二叉树的最近公共祖先 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。*/
    TreeNode* lowestCommonAncestor( TreeNode* root, TreeNode* p, TreeNode* q ) {

        if ( root == nullptr || root == p || root == q ) {
            return root;
        }
        TreeNode* left  = lowestCommonAncestor( root->left, p, q );
        TreeNode* right = lowestCommonAncestor( root->right, p, q );
        if ( left == nullptr && right == nullptr ) {
            return nullptr;
        }
        else if ( left == nullptr && right != nullptr ) {
            return right;
        }
        else if ( left != nullptr && right == nullptr ) {
            return left;
        }
        else {
            return root;
        }
    }

    // 深度遍历：栈，递归
    int maxDepth( TreeNode* root ) {
        if ( root == nullptr ) {
            return 0;
        }

        if ( root->left == nullptr && root->right == nullptr ) {
            return 1;
        }

        return 1 + std::max( maxDepth( root->left ), maxDepth( root->right ) );
    }

    // 层序遍历：队列
    int maxDepth2( TreeNode* root ) {
        if ( root == nullptr ) {
            return 0;
        }

        queue< TreeNode* > qu;
        int                result = 0;

        qu.push( root );

        while ( !qu.empty() ) {
            queue< TreeNode* > temp;
            while ( !qu.empty() ) {
                if ( qu.front()->left != nullptr ) {
                    temp.push( qu.front()->left );
                }
                if ( qu.front()->right != nullptr ) {
                    temp.push( qu.front()->right );
                }
                qu.pop();
            }
            qu = temp;

            result++;
        }

        return result;
    }

    // 后序遍历 判断是否是平衡二叉树
    bool isBalanced( TreeNode* root ) {
        return dsp( root ) == -1 ? false : true;
    }
    // 如果是平衡二叉树返回高度，如果不是平衡二叉树返回-1,并剪枝
    int dsp( TreeNode* root ) {

        if ( root == nullptr ) {
            return 0;
        }

        int left = dsp( root->left );
        if ( left == -1 ) {
            return -1;
        }

        int right = dsp( root->right );
        if ( right == -1 ) {
            return -1;
        }

        if ( abs( left - right ) > 1 ) {
            return -1;
        }

        return max( right, left ) + 1;
    }

private:
    unordered_map< int, int > m_inorderMap;
};

#endif /*_TREE_*/